package sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;

public class QuickSort {
    public static <T extends Comparable> List<T> sort(List<T> nums) throws ExecutionException, InterruptedException {
        List<T> result = new ArrayList<>(nums);
        //innerSort(result, 0, result.size());
        ForkJoinTask task = ForkJoinPool.commonPool().submit(new MyQuickSort<>(result, 0, result.size()));
        task.get();
        return result;
    }

    // 左闭右开
    private static <T extends Comparable> void innerSort(List<T> nums, int begin, int end) {
        // 0. 仅有一个元素时直接退出
        if (begin >= end) return;
        // 1. 选择第一个数据作为基准,进行分拆
        T base = nums.get(begin);
        // 2. 扫描剩余元素，按基准进行分隔
        int l = begin, r = end - 1;
        while (l < r) {
            // 从右往左扫比base小的元素
            while (l < r && nums.get(r).compareTo(base) >= 0) r--;
            if (l < r) {
                nums.set(l, nums.get(r));
            }
            // 从左向右扫比base大的元素
            while (l < r && nums.get(l).compareTo(base) <= 0) l++;
            if (l < r) {
                nums.set(r, nums.get(l));
            }
        }
        nums.set(l, base);
        // 3. 以base为基准进行分拆
        innerSort(nums, begin, l);
        innerSort(nums, l + 1, end);
    }

    public void quickSort(int[] arr, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int mid = arr[begin];

        int left = begin;
        int right = end;
        while (left < right) {
            //右边找小的
            while (left < right && arr[right] >= mid) {
                right--;
            }
            //左边找大的
            while (left < right && arr[left] <= mid) {
                left++;
            }
            //交换
            if (left < right) {
                int tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
            }
        }
        //设置参考位
        if (mid >= arr[left]) {
            int tmp = arr[left];
            arr[left] = mid;
            arr[begin] = tmp;
        }
        quickSort(arr, begin, left - 1);
        quickSort(arr, left + 1, end);
    }

    public static void main(String[] args) {
        int[] nums = new int[]{
                884688278, 387052570, 77481420, 537616843, 659978110, 215386675, 604354651, 64838842, 830623614, 544526209, 292446044, 570872277, 946770900, 411203381, 445747969, 480363996, 31693639, 303753633, 261627544, 884642435, 978672815, 427529125, 111935818, 109686701, 714012242, 691252458, 230964510, 340316511, 917959651, 544069623, 193715454, 631219735, 219297819, 151485185, 986263711, 805374069, 915272981, 493886311, 970466103, 819959858, 733048764, 393354006, 631784130, 70309112, 513023688, 17092337, 698504118, 937296273, 54807658, 353487181, 82447697, 177571868, 830140516, 536343860, 453463919, 998857732, 280992325, 13701823, 728999048, 764532283, 693597252, 433183457, 157540946, 427514727, 768122842, 782703840, 965184299, 586696306, 256184773, 984427390, 695760794, 738644784, 784607555, 433518449, 440403918, 281397572, 546931356, 995773975, 738026287, 861262547, 119093579, 521612397, 306242389, 84356804, 42607214, 462370265, 294497342, 241316335, 158982405, 970050582, 740856884, 784337461, 885254231, 633020080, 641532230, 421701576, 298738196, 918973856, 472147510, 169670404
                //5, 2, 3, 1, 4
        };
        new QuickSort().quickSort(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.println(num + ",");
        }
    }
}

class MyQuickSort<T extends Comparable> extends RecursiveTask {

    private int begin, end;
    private List<T> nums;

    public MyQuickSort(List<T> nums, int begin, int end) {
        this.nums = nums;
        this.begin = begin;
        this.end = end;
    }

    @Override
    protected Object compute() {
        // 0. 仅有一个元素时直接退出
        if (begin >= end) return null;
        // 1. 选择第一个数据作为基准,进行分拆
        T base = nums.get(begin);
        // 2. 扫描剩余元素，按基准进行分隔
        int l = begin, r = end - 1;
        while (l < r) {
            // 从右往左扫比base小的元素
            while (l < r && nums.get(r).compareTo(base) >= 0) r--;
            if (l < r) {
                nums.set(l, nums.get(r));
            }
            // 从左向右扫比base大的元素
            while (l < r && nums.get(l).compareTo(base) <= 0) l++;
            if (l < r) {
                nums.set(r, nums.get(l));
            }
        }
        nums.set(l, base);
        // 3. 以base为基准进行分拆
        final ForkJoinTask fork = new MyQuickSort<>(nums, begin, l).fork();
        final ForkJoinTask fork1 = new MyQuickSort<>(nums, l + 1, end).fork();
        fork.join();
        fork1.join();
        return null;
    }
}